package com.itheima.exerciseTest.test20_29;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

/*
   (1)生成10个1至100之间的随机整数(不能重复)，存入一个List集合(可以先不使用泛型，泛型明天讲)
   (2)编写方法对List集合进行排序,禁用Collections.sort方法和TreeSet
   (3)然后利用迭代器遍历集合元素并输出
   (4)如：15 18 20 40 46 60 65 70 75 91
        */
public class Test28$$ {
    public static void main(String[] args) {
        // (1)生成10个1至100之间的随机整数(不能重复)，存入一个List集合(可以先不使用泛型，泛型明天讲)
        List<Integer> list = setList();
        // List<Integer> list = setListTest();

        // List<Integer> list = setListTest();
        // 排序前
        printList(list);

        System.out.println("\n=============================");

        // (2)编写方法对List集合进行排序,禁用Collections.sort方法和TreeSet
        // 快排
        list = sort(list, 0, list.size() - 1);

        // 冒泡
        // sortTest(list);

        // (3)然后利用迭代器遍历集合元素并输出
        // 排序后
        printList(list);
    }

    // 生成10个1至100之间的随机整数(不能重复)，存入一个List集合
    // 1，
    public static List<Integer> setListTest() {
        Random r = new Random();

        int[] arr = new int[10];

        arr[0] = r.nextInt(100) + 1;
        int count = 1;

        while (count < 10) {
            boolean boo = false;

            int tamp = r.nextInt(100) + 1;

            for (int i = 0; i < count; i++) {
                if (tamp == arr[i]) {
                    boo = false;
                    break;
                }
                boo = true;
            }

            if (boo == true) {
                arr[count] = tamp;
                count++;
            }
        }

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            list.add(arr[i]);
        }
        return list;

    }

    // 2，list.contains()
    public static List<Integer> setList() {
        Random r = new Random();
        List<Integer> list = new ArrayList<>();
        list.add((r.nextInt(100) + 1));

        while (list.size() <= 10) {
            int number = r.nextInt(100) + 1;
            if (list.contains(number)) continue;
            list.add(number);
        }
        return list;
    }

    // 排序
    // 1，快排
    public static List<Integer> sort(List<Integer> list, int left, int right) {
        int[] arr = new int[list.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }

        sort(arr, left, right);

        list.clear();
        for (int i = 0; i < arr.length; i++) {
            list.add(arr[i]);
        }
        return list;
    }

    public static void sort(int[] arr, int left, int right) {
        if (left > right) return;

        int left0 = left;
        int right0 = right;
        int middle = arr[left];

        while (left < right) {
            while (arr[right] >= middle && right > left) {
                right--;
            }
            while (arr[left] <= middle && left < right) {
                left++;
            }
            int tamp = arr[left];
            arr[left] = arr[right];
            arr[right] = tamp;
        }
        int tamp = arr[left0];
        arr[left0] = arr[left];
        arr[left] = tamp;

        sort(arr, left0, left - 1);
        sort(arr, left + 1, right0);

    }

    // 2，冒泡排序
    public static void sortTest(List<Integer> list) {
        for (int i = 1; i < list.size(); i++) {
            for (int j = 0; j < list.size() - i; j++) {
                if (list.get(j) > list.get(j + 1)) {
                    int tamp = list.get(j);
                    list.set(j, list.get(j + 1));
                    list.set(j + 1, tamp);
                }
            }
        }
    }

    // 迭代器打印
    public static void printList(List<Integer> list) {
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) System.out.print(it.next() + " ");
    }

}
